package BinaryTreePackage2;

import TreePackage.Tree;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author Lzm
 * @version 1.0
 */
public class Traversal2_ {
  List<Integer> result = new ArrayList<>();
  Stack<TreeNode> stack = new Stack<>();

  @Test
  public void preorderTraversalTest(){
    TreeNode root = new TreeNode(5);
    TreeNode node1 = new TreeNode(4);
    TreeNode node2 = new TreeNode(6);
    TreeNode node3 = new TreeNode(2);
    TreeNode node4 = new TreeNode(1);
    root.right = node2;
    root.left = node1;
    node1.left = node3;
    node1.right = node4;
    List<Integer> list = inorderTraversal(root);
    System.out.println(list.toString());
  }
  // 1. 前序遍历
  public List<Integer> preorderTraversal(TreeNode root) {
    if (root == null){
      return result;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while(!stack.isEmpty()){
      TreeNode temp = stack.pop();
      if (temp != null){
        result.add(temp.val);
      }
      else{
        continue;
      }
      if (temp.right != null)
        stack.push(temp.right);
      if (temp.left != null)
        stack.push(temp.left);
    }
    return result;
  }
  // 1. 前序遍历
  public List<Integer> inorderTraversal(TreeNode root) {
    TreeNode temp = root;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(temp);
    while(temp != null && !stack.isEmpty()){
      if (temp.left != null){
        stack.push(temp.left);
        temp = temp.left;
      }
      else{
        temp = stack.pop();
        result.add(temp.val);
        temp = temp.right;
      }
    }
    return result;
  }
}
